1. Field of the Invention
The present invention relates to an asynchronous arbiter, and more particularly, to an asynchronous arbiter capable of such a function that in the case where a plurality of request signals are so asynchronously generated as to vie with each other from a plurality of mutually independent signal sources towards a common resource, the respective request signals are transmitted in succession to the resource in the order of their generation by giving the highest priority to the request signal generated earliest, and an acknowledgement signal from the resource is sent to the signal source having the highest priority and thereafter to the remaining signal sources in descending order of priority.
2. Description of the Prior Art
In a parallel information processing system, a plurality of processors operating quite independently of each other may share a common resource such as a memory, a data bus, an I/O device or an arithmetic unit. Consequently, at various times during system operation there occurs a situation where request signals for the use of the common resource by two or more processors are generated in overlapping time periods, and as a result, these request signals conflict with each other.
As a specific example, in recent large-sized and highly-improved parallel information processing systems, this situation often occurs, and therefore, in order to enhance the efficiency of the system, the problem of resource allocation becomes most important. Generally, in a parallel information processing system in which no particular order of the priority is predetermined for the respective processors and in which they are serviced on an equal preference basis, the earlier generation of the request signal from each processor becomes a basis for the resource allocation. More particularly, among the processors from which a plurality of requests for using a resource are generated, the first use is acknowledged for the processor generating the earliest request signal, while the other processors are left waiting, and thereafter, when the use of the resource by the first acknowledged processor has been finished, and when the request signal has disappeared, the resource use by the processor producing the second earliest request signal and kept waiting up to that moment is acknowledged. However, in such an informaion processing system, the respective request signals always vie asynchronously, and as a result, this situation may cause considerable difficulty in the system operation. Therefore, it is considered that the realization of a simple asynchronous arbiter capable of dealing with such conflicts between the request signals will greatly contribute to the enhancement of the reliability and the improvement of the efficiency of the system.
As will be apparent from the above-described background of the art, the use and the application of such an asynchronous arbiter is very wide, or, in other words, the arbiter is applicable to any situation where conflicts may occur between the asynchronous signals in not only computer systems, but also in communication systems in general. For instance, the switching of telephone lines, the interface control in a computer network, the page swapping in a virtual memory system and the data bus control in a multiprocessing system, etc., are all fields wherein an asynchronous arbiter can be used.
However, conventional asynchronous arbiters have disadvantages such that the number of needed elements is typically large because the circuit construction is complicated and that the resource allocation cannot always be done in the order of the generation of the request signals. For instance, one of the conventional asynchronous arbiters is disclosed in a paper entitled "Asynchronous Arbiters" by William W, Plummer and published in IEEE Transactions On Computers, Vol. C-21, No. 1, Pages 37-42, and its circuit construction is illustrated in FIG. 11 on Page 41 of that reference. In the conventional arbiter as shown therein, when request signals (R.sub.1 and R.sub.2) are so generated from a plurality of processors as to vie with each other, an input gate is closed by an AWAIT signal produced as a logical sum of the signals representing the generation of the request signals, resulting in blocking of the subsequent request signals, so that while the request signal generated earliest is occupying a resource, the second and subsequent orders of the preference in vying cannot be held. Accordingly, the basic principle of the successive acknowledgement for resource use in sequence starting from the request signal generated earliest is not always maintained. In other words, such a conventional arbiter as that disclosed by Plummer has a disadvantage such that among the orders of the preference in vying of the request signals, the second and subsequent orders of the preference will disappear. Also, at the time point where said input gate has been closed, the candidates that can be a winner in the competition generally consist of a plurality of the request signals (R.sub.1 and R.sub.2), and among these candidates, the earliest winner must be decided according to a predetermined order of preference by means of a flip-flop 2LAST. As a result, this conventional asynchronous arbiter also has disadvantages such that the operation speed becomes low, and that a lot of logic elements are needed.